#include <bits/stdc++.h>

using namespace std;

// 字符串哈希得到子串哈希
// 利用字符串哈希的便利性替代KMP算法
// 测试链接 : https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/

class Solution 
{
public:
	// 如下代码是字符串哈希的原理和模版
	// 比如，base = 499, 也就是课上说的选择的质数进制
	// 再比如字符串s如下
	// " c a b e f "
	//   0 1 2 3 4
	// hash[0] = 3 * base的0次方
	// hash[1] = 3 * base的1次方 + 1 * base的0次方
	// hash[2] = 3 * base的2次方 + 1 * base的1次方 + 2 * base的0次方
	// hash[3] = 3 * base的3次方 + 1 * base的2次方 + 2 * base的1次方 + 5 * base的0次方
	// hash[4] = 3 * base的4次方 + 1 * base的3次方 + 2 * base的2次方 + 5 * base的1次方 + 6 *
	// base的0次方
	// hash[i] = hash[i-1] * base + s[i] - 'a' + 1，就是上面说的意思
	// 想计算子串"be"的哈希值 -> 2 * base的1次方 + 5 * base的0次方
	// 子串"be"的哈希值 = hash[3] - hash[1] * base的2次方(子串"be"的长度次方)
	// hash[1] = 3 * base的1次方 + 1 * base的0次方
	// hash[1] * base的2次方 = 3 * base的3次方 + 1 * base的2次方
	// hash[3] = 3 * base的3次方 + 1 * base的2次方 + 2 * base的1次方 + 5 * base的0次方
	// hash[3] - hash[1] * base的2次方 = 2 * base的1次方 + 5 * base的0次方
	// 这样就得到子串"be"的哈希值了
	// 子串s[l...r]的哈希值 = hash[r] - hash[l-1] * base的(r-l+1)次方，就是上面说的意思
    static const int MAXN = 100005;
    int base = 131;
    unsigned long long p[MAXN], h[MAXN];

    void build(string& s, int n)
    {
        p[0] = 1;
        for(int i = 1; i < n; ++i) p[i] = p[i - 1] * base;
        h[0] = s[0] - 'a' + 1;
        for(int i = 1; i < n; ++i)
        {
            h[i] = h[i - 1] * base + s[i] - 'a' + 1;
        }
    }

    // 返回s[l...r]的哈希值
    unsigned long long hash(int l, int r)
    {
        long ans = h[r];
        if(l > 0) ans -= h[l - 1] * p[r - l + 1];
        return ans;
    }

    int strStr(string s1, string s2) 
    {
        int n = s1.size(), m = s2.size();
        build(s1, n);
        unsigned long long h2 = s2[0] - 'a' + 1;
        for(int i = 1; i < m; ++i)
        {
            h2 = h2 * base + s2[i] - 'a' + 1;
        }
        for(int l = 0, r = m - 1; r < n; ++l, ++r)
        {
            if(hash(l, r) == h2) return l;
        }
        return -1;
    }
};


class Solution 
{
private:
    static const int MAXN = 10010;
    using ull = unsigned long long;
    int n, P = 131;
    ull p[MAXN], h[MAXN];

    // 预处理出 s 的所有前缀的哈希值
    void init(string& s)
    {
        h[0] = 0, p[0] = 1;
        for(int i = 1; i <= n; ++i)
        {
            p[i] = p[i - 1] * P;
            h[i] = h[i - 1] * P + s[i - 1];
        } 
    }

public:
    int strStr(string s1, string s2) 
    {
        n = s1.size();
        init(s1);

        ull hashVal = 0;
        int m = s2.size();
        // 计算 s2 的哈希值
        for(int i = 0; i < m; ++i)
        {
            hashVal = hashVal * P + s2[i];
        }
        
        for(int i = 0; i <= n - m; ++i)
        {
            // 子串 [i, i + m - 1] 的哈希值
            if(h[i + m] - h[i] * p[m] == hashVal) return i;
        }
        return -1;
    }
};